package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _20_valid_par {
    
    /**
     * 来瞧瞧，看某人自作聪明把简单题做错的故事
     * */
    public boolean isValid_ERROR(String s) {
        if (s.length() % 2 != 0) return false;
        int par = 0, square = 0, brace = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(': par++; break;
                case ')': par--; if (par < 0) return false; break;
                case '[': square++; break;
                case ']': square--; if (square < 0) return false; break;
                case '{': brace++; break;
                case '}': brace--; if (brace < 0) return false; break;
            }
        }
        return par == 0 && square == 0 && brace == 0;
    }
    
    /**
     * 没有更好的写法了吗
     * */
    public boolean isValid2(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        stack.push('\0');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(': case '[': case '{': stack.push(c); break;
                case ')': if (stack.pop() != '(') return false; break;
                case ']': if (stack.pop() != '[') return false; break;
                case '}': if (stack.pop() != '{') return false; break;
            }
        }
        return stack.size() == 0;
    }
    
    /**
     * 没啥意思很烦
     * hashmap 元素还写反了！
     * */
    static Map<Character, Character> map = new HashMap<>();
    static {
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
    }
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
        LinkedList<Character> stack = new LinkedList<>();
        stack.push('?');
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (map.get(s.charAt(i)) != stack.peek())
                    return false;
                stack.pop();
            } else{
                stack.push(s.charAt(i));
            }
        }
        return stack.size() == 1;
    }
    
}
